class Node:             #定义元素
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:       #定义二叉树
    def __init__(self):
        self.root = None
        self.help_queue = []  # 辅助队列

    def level_build_tree(self, node: Node):
        if self.root is None:  # 树根为空
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:  # 如果当前的父亲左孩子是None
                self.help_queue[0].lchild = node  # 放入左孩子
            else:
                self.help_queue[0].rchild = node  # 放入右孩子
                self.help_queue.pop(0)  # 当前父亲满了，出队

    def pre_order(self, current_node: Node):    #前序遍历
        if current_node:
            print(current_node.elem, end=' ')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self, current_node: Node):    #中序遍历
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.elem, end=' ')
            self.mid_order(current_node.rchild)

    def last_order(self, current_node: Node):   #后序遍历
        if current_node:
            self.last_order(current_node.lchild)
            self.last_order(current_node.rchild)
            print(current_node.elem, end=' ')

    def level_order(self):                  #层次遍历
        help_queue = []
        help_queue.append(self.root)  # 树根入队
        while help_queue:
            out_node: Node = help_queue.pop(0)  # 出队，:Node为out_node的说明
            print(out_node.elem,end=' ')  # 打印出队元素的元素值
            if out_node.lchild:
                help_queue.append(out_node.lchild)
            if out_node.rchild:
                help_queue.append(out_node.rchild)


if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1, 21):               #1-20元素构建二叉树
        new_node = Node(i)  # 实例化结点
        tree.level_build_tree(new_node)  # 把结点放入树中
    tree.pre_order(tree.root)  # 前序遍历
    print()
    tree.mid_order(tree.root)
    print()
    tree.last_order(tree.root)
    print()
    tree.level_order()


print(" \n")
print('-'*50)


student_tuples = [
    ('jane', 'B', 12),
    ('john', 'A', 15),
    ('dave', 'B', 10),
]

# lambda表达式，就是匿名函数，后跟简短的函数表达式
# 匿名函数好处，提高编写效率，提高阅读速度
print(sorted(student_tuples, key=lambda x: x[0]))
print(sorted(student_tuples, key=lambda x: x[1]))
print(sorted(student_tuples, key=lambda x: x[2]))



print('-'*50)


class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age

    def __repr__(self):
        """
        与__str__相比能返回非字符串类型
        """
        return repr((self.name, self.grade, self.age))


student = Student('john', 'A', 15)
student_objects = [
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
]

print('-' * 50)

print(sorted(student_objects,key=lambda student:student.age))

from operator import itemgetter, attrgetter         #导入系统自带的模块
print('使用operator系列')
print(sorted(student_tuples, key=itemgetter(0)))
print(sorted(student_objects,key=attrgetter('age')))
print('使用operator系列,多列排序')
print(sorted(student_tuples, key=itemgetter(1,2)))
print(sorted(student_tuples, key=lambda x: (x[1],-x[2]))) #第一列升序，第二列降序，降序通过负号实现
print(sorted(student_objects, key=attrgetter('grade', 'age'),reverse=True))

print('查看排序稳定性')
data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
print(sorted(data, key=itemgetter(0)))

mydict = { 'Li'   : ['M',7],
           'Zhang': ['E',2],
           'Wang' : ['P',3],
           'Du'   : ['C',2],
           'Ma'   : ['C',9],
           'Zhe'  : ['H',7] }

print(sorted(mydict.items(),key=lambda x:x[1][1]))


print('-'*50)


gameresult = [
    { "name":"Bob", "wins":10, "losses":3, "rating":75.00 },
    { "name":"David", "wins":3, "losses":5, "rating":57.00 },
    { "name":"Carol", "wins":4, "losses":5, "rating":57.00 },
    { "name":"Patty", "wins":9, "losses":3, "rating": 71.48 }]
print(sorted(gameresult,key=lambda x:x['rating']))
print(sorted(gameresult , key=itemgetter("rating","name")))